package leetcode;

import Tree.BinaryTreeCreate;
import Tree.CreateByPreAndIn;
import Tree.PrintByDown;
import Tree.TreeNode;

public class BuildTreeByPreAndIn {

	public static void main(String[] args) {
		int[] pre = {1, 2, 3};
		int[] in = {3, 1,2};
		TreeNode node = buildTree(pre, in);
//		BinaryTreeCreate.inOrder(node);
		PrintByDown.printFromTopToBottom(node);
	}
	//通过前序和中序来创建子树
	public static TreeNode buildTree(int[] preorder, int[] inorder) {
		if (preorder == null || preorder.length <= 0 || inorder == null
				|| inorder.length <= 0 || preorder.length != inorder.length) {
			return null;
		}
		int value = preorder[0];
		TreeNode node = new TreeNode(value);
		int i;
		for (i = 0; i < inorder.length; i++) {
			if (inorder[i] == value) {
				break;
			}
		}
		if (i >= inorder.length) {
			return null; // 找不到匹配的，说明不存在
		}
		int[] leftPre = new int[i], leftIn = new int[i];
		int[] rightPre = new int[inorder.length - 1 - i], rightIn = new int[inorder.length
				- 1 - i];
		// 构建左边的数组
		for (int j = 0; j < i; j++) {
			leftPre[j] = preorder[j + 1];
			leftIn[j] = inorder[j];
		}
		// 构建右边的数组
		for (int j = 0; j < inorder.length - 1 - i; j++) {
			rightPre[j] = preorder[j + i + 1];
			rightIn[j] = inorder[j + i + 1];
		}
		node.left = buildTree(leftPre, leftIn);
		node.right = buildTree(rightPre, rightIn);
		return node;
	}
	//通过后序和中序来创建树
	public static TreeNode buildTree2(int[] inorder, int[] postorder) {
		if (postorder == null || postorder.length <= 0 || inorder == null
				|| inorder.length <= 0 || postorder.length != inorder.length) {
			return null;
		}
		int value = postorder[postorder.length - 1];//最后一个是根节点
		TreeNode node = new TreeNode(value);
		int i;
		for (i = 0; i < inorder.length; i++) {
			if (inorder[i] == value) {
				break;
			}
		}
		if (i >= inorder.length) {
			return null; // 找不到匹配的，说明不存在
		}
		int[] leftPost = new int[i], leftIn = new int[i];
		int[] rightPost = new int[inorder.length - 1 - i], rightIn = new int[inorder.length - 1 - i];
		// 构建左边的数组
		for (int j = 0; j < i; j++) {
			leftPost[j] = postorder[j];
			leftIn[j] = inorder[j];
		}
		// 构建右边的数组
		for (int j = 0; j < inorder.length - 1 - i; j++) {
			rightPost[j] = postorder[j + i];
			rightIn[j] = inorder[j + i + 1];
		}
		node.left = buildTree(leftIn, leftPost);
		node.right = buildTree(rightIn, rightPost);
		return node;
	}
}
